//3部手机，1000层楼，最坏需要测试几次
//该算法可用递归+二分进行优化，这里作为填空题直接暴力递归即可

public class Main2 {

    private static int[][] dp=new int[3000][3000];
    public static void main(String[] args) {
        System.out.println(dp(3, 1000));

    }
    private static int dp(int m,int n) {
        int ans = 1000;
        if(m==1) {return n;}
        if(n==0) {return 0;}

        if((dp[m][n]>=1)) {return dp[m][n];}

        //遍历楼层数
        for(int i=1;i<=n;i++) {
            //i是在第i层是否摔碎的交界
            //分手机碎和没碎两种情况写状态转移方程
            //min表示“至少”，max表示“最坏”
            ans = Math.min(Math.max(dp(m, n-i), dp(m-1, i-1))+1,ans);
            //表示记录过
            dp[m][n]=ans;
        }

        return ans;
    }
}